Na omotu čokolade sa lešnikom piše da proizvođač garantuje da se u kvadratu od a × a kockica sigurno nalazi bar jedan lešnik. Nikola je kupio jednu čokoladu i zanima ga koji je najveći kvadrat koji može pronaći tako da se u donjem desnom uglu kvadrata nalazi lešnik. Napisati program koji nalazi najveći kvadrat sačinjen od x × x kockica tako da sadrži samo jedan lešnik, i taj lešnik se nalazi u poslednjoj kockici tog kvadrata.

Ulaz

Sa standardnog ulaza se učitava ceo broj n (1 < n < 10³), a zatim i n² brojeva (0 ili 1) koji predstavljaju da li određena kockica čokolade sadrži lešnik ili ne.

Izlaz

Ispisati jedan broj, koji predstavlja dužinu stranice najvećeg traženog kvadrata.

Primer

Ulaz

3
0 1 0
1 0 0
0 0 1

Izlaz

2

Objašnjenje

Traženi kvadrat dimenzije 2 × 2 je oblika:

0 0
0 1

i nalazi se u donjem desnom uglu.

Primer

Ulaz

4
0 0 0 1
0 1 0 1
0 0 0 0
1 1 1 1

Izlaz

2